package 动态规划.背包问题;

/**
 * @author admin
 * @version 1.0.0
 * @ClassName 完全背包.java
 * @Description TODO
 * @createTime 2020年11月14日 10:21:00
 * 有 N 种物品和一个容量是 V 的背包，每种物品都有无限件可用。
 *
 * 第 i 种物品的体积是 vi，价值是 wi。
 *
 * 求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
 * 输出最大价值。
 */
public class 完全背包 {
    class  solution{
        public int erwei(int[] v,int[] w,int n,int m){
            int[][] dp=new int[n+1][m+1];
            for(int i=1;i<=n;i++) {
                for (int j = 0; j <= m; j++) {
                    dp[i][j] = dp[i - 1][j];
                    if (v[i - 1] <= j) {
                        dp[i][j] = Math.max(dp[i][j], dp[i][j - v[i]] + w[i - 1]);
                    }
                }
            }


            return dp[n][m];
        }


        public  int youhua(int[] v,int[] w,int n,int m){
            int[] dp=new int[m+1];
            for(int i=1;i<=n;i++){
                for(int j=v[i];j<=m;j++){
                    dp[j]=Math.max(dp[j],dp[j-v[i]]+w[j]);
                }
            }

            return dp[m];
        }
    }
}
